package 动态规划;

public class No312戳气球 {

    /**
     * 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
     * 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。
     *  这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。
     * 如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
     * 求所能获得硬币的最大数量。
     *
     * 示例 1：
     * 输入：nums = [3,1,5,8]
     * 输出：167
     * 解释：
     * nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
     * coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
     * 示例 2：
     * 输入：nums = [1,5]
     * 输出：10
     *  
     * 提示：
     * n == nums.length
     * 1 <= n <= 500
     * 0 <= nums[i] <= 100
     */

    /**
     * 此题较难,难点在于 dp 状态转义方程如何定义。
     * 参考题解如是说道:
     * dp[i][j]表示范围在(i,j)开区间内所能得到的最大银币数量。
     *
     */
    public int maxCoins(int[] nums) {

        int n = nums.length;

        // 创建一个辅助数组，并在首尾各添加1，方便处理边界情况
        int[] temp = new int[n+2];
        temp[0] = 1;
        temp[n+1] = 1;

        for(int i=0; i<n; i++){
            temp[i+1] = nums[i];
        }

        int[][] dp = new int[n+2][n+2];

        /**
         * 从 length=3 开始,一直dp到length=n.length;[3..n]
         * 并且每个for都从 [0..n]开始,并且每个[0..n]开始都选中其中一个(最后一个气球)k开始乘两边+left+right
         */

        //从区间为 3 开始到 n+2
        for (int i = 3; i <= temp.length; i++) {

            //左起点
            for (int j = 0; j <= temp.length-i; j++) {
                int res=0;
                //最后一个戳破的气球,开区间-1
                for (int k = j+1; k < j+i-1; k++) {
                    //左边界这么长
                    int left=dp[j][k];
                    //k起,到右边界这么长
                    int right=dp[k][i+j-1];
                    res=Math.max(res,left+right+temp[j+i-1]*temp[j]*temp[k]);
                }
                dp[j][i+j-1] = res;
            }

        }

        return dp[0][n+1];
    }

    public static void main(String[] args) {
        No312戳气球 n=new No312戳气球();
        int[] arr={3,2,5,8};
        int result = n.maxCoins(arr);
        System.out.println(result);
    }

}
